package leetcode_1000;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 周杨
 * 2018年11月17日 下午8:45:47  在线选举某个人为第一名 给定时间投票人 问在i时谁是第一名
 * OnlineElection_911.java 
 * description:不必用优先队列 只需要记录最高次数的 然后把res保存 
 */
public class OnlineElection_911 {

class Vote {
    int person, time;
    Vote(int p, int t) {
        person = p;
        time = t;
    }
}
	List<Vote> A;
    public OnlineElection_911(int[] persons, int[] times) {
        A = new ArrayList<Vote>();
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        int leader = -1;  // current leader
        int m = 0;  // current number of votes for leader

        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i], t = times[i];
            int c = count.getOrDefault(p, 0) + 1;
            count.put(p, c);

            if (c >= m) {
                if (p != leader) {  // lead change
                    leader = p;
                    A.add(new Vote(leader, t));
                }

                if (c > m) m = c;
            }
        }
    }

    public int q(int t) {
        int lo = 1, hi = A.size();
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A.get(mi).time <= t)
                lo = mi + 1;
            else
                hi = mi;
        }

        return A.get(lo - 1).person;
    }
	
	
	public static void main(String[] args) {
		int now[]=new int[] {1,3,4,6,7,9,10};
		System.out.println(Arrays.binarySearch(now, 5));
	}
	/*
	static class Vote{
		int time;//被投了多少次
		int id;//这是哪个人
		public Vote(int time,int id) {
			this.time=time;
			this.id=id;
		}
	}
	int []res;
	int []times;*/
	/**
	 * 不知道哪里写错了
	 *//*
	public OnlineElection_911(int[] persons, int[] times) {
        PriorityQueue<Vote> queue=new PriorityQueue<Vote>(new Comparator<Vote>() {//当前的排序队列

		@Override
		public int compare(Vote o1, Vote o2) {
			if(o1.time<o2.time)
				return 1;
			return -1;
		}
        });
        Map<Integer,Vote> map=new HashMap<Integer,Vote>();//记录当前的Id对应的Vote
        this.times=times;
        this.res=new int[times.length];
        for(int i=0;i<persons.length;++i) {
        	Vote vote=map.get(persons[i]);
        	if(vote==null) {
        		vote=new Vote(1, persons[i]);
        	}
        	else {
        		queue.remove(vote);
        		vote.time++;
        	}
    		queue.offer(vote);
        	map.put(persons[i], vote);
        	res[i]=queue.peek().id;
        }
    }
    
    public int q(int t) {
        int search=Arrays.binarySearch(times, t);
        if(search<0) {//没有找到
        	search=-(search+2);
        }
        return res[search];
    }*/
}
